#pragma once

#include <iostream>
#include <deque>
#include <cassert>
#include <initializer_list>

// 获取 i 节点的父子节点索引
#define PARENT(i) ((((i) + 1) >> 1) - 1)
#define LEFTCHILD(i) ((((i) + 1) << 1) - 1)
#define RIGHTCHILD(i) (((i) + 1) << 1)

/**
 * @file Heap.h
 * @author xingyifan
 * @date 2022-12-26 09:55
 *
 * @description: 默认最大堆：某个节点的值最多和父节点一样大。根节点是最大的节点
 */

template <class T, typename Ty = std::greater<T>>
class Heap
{
protected:
    bool m_valid; // 记录是否建堆，即堆是否有效
    std::deque<T> m_value;

public:
    Heap() : m_valid(false) {}

    // 初始化列表构造
    Heap(std::initializer_list<T> l) : m_valid(true)
    {
        for (auto it = l.begin(); it != l.end(); ++it)
            m_value.push_back(*it);

        // 初始化时立刻建堆
        build_heap();
    }

    // 降堆，将指定节点逐渐降低到正确位置
    void shiftdown(int i, int remain)
    {
        int l = LEFTCHILD(i);
        int r = RIGHTCHILD(i);
        int result = i;

        // 定义比较对象
        Ty compare;
        if (l < remain && compare(m_value[l], m_value[result]))
            result = l;
        if (r < remain && compare(m_value[r], m_value[result]))
            result = r;
        // 如果 result 对应的元素不在正确的位置上就交换
        if (result != i)
        {
            T tmp = m_value[i];
            m_value[i] = m_value[result];
            m_value[result] = tmp;
            shiftdown(result, remain);
        }
    }

    // 排序算法，将最大堆中的元素按照从小到大的顺序排列，最小堆中的元素会按照从大到小的顺序排列
    void sort()
    {
        // 如果堆无效，应当报错，不能排序
        assert(m_valid);

        // 排序算法
        int remain = m_value.size();
        for (int i = m_value.size() - 1; i > 0; i--)
        {
            double tmp = m_value[i];
            m_value[i] = m_value[0];
            m_value[0] = tmp;

            remain--;
            shiftdown(0, remain);
        }

        // 排序后堆无效
        m_valid = false;
    }

    // 重新建堆
    void build_heap()
    {
        // 建堆，重复降堆，实现最大堆
        for (int i = PARENT(m_value.size() - 1); i >= 0; i--)
            shiftdown(i, m_value.size());

        // 建堆后堆有效
        m_valid = true;
    }

    // 从头部推入元素，然后建堆，将 value 下降到正确的位置
    void push_front(T value)
    {
        m_value.push_front(value);

        // 如果原来是堆，直接降堆；否则重新建堆
        if (m_valid)
            shiftdown(0, m_value.size());
        else
            build_heap();
    }

    T front() const { return m_value.front(); } // 只允许获得头部元素，最大堆获得最大元，最小堆获得最小元
    int size() const { return m_value.size(); } // 获得堆的规模
};